class Solution:
    def mySqrt(self, x: int) -> int:

        left = 0
        right = x
        while left <= right:
            mid = left + (right - left) // 2
            if mid ** 2 > x:
                right = mid - 1
            elif mid ** 2 < x:
                left = mid + 1
            else:
                return mid
        # 突破结界的时候left大1减去就好了
        return left - 1

class Solution:
    def mySqrt(self, x: int) -> int:
        l, r, ans = 0, x, -1
        while l <= r:
            mid = (l + r) // 2
            if mid * mid <= x:
                ans = mid
                l = mid + 1
            else:
                r = mid - 1
        return ans
'''
更清晰，返回的是满足条件的最后一个res
'''
class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x
        res = -1
        while left <= right:
            mid = (left + right)//2
            if mid**2 <= x:
                res = mid
                left = mid + 1
            else:
                right = mid - 1
        return res
